package com.wtgroup.demo.mianshi.算法.并查集;

import org.apache.commons.math3.analysis.solvers.BisectionSolver;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/21 9:34
 */
public class D1 {

    /**
     * 这里是为了方便理解, 用的哈希表. 实际做题时, 用数组. 利用输入的元素索引.
     * 数组方式比哈希表方式快一个量级.
     * @param <V>
     */
    public static class UnionSet<V> {
        // a -> parent
        private Map<Node<V>, Node<V>> parents = new HashMap<>();
        // root -> count , 只含根节点
        private Map<Node<V>, Integer> sizeMap = new HashMap<>();
        // 用户传入的值 V->Node, 用户透明
        private Map<V, Node<V>> nodes = new HashMap<>();

        public UnionSet(List<V> values) {
            for (V val : values) {
                Node<V> node = new Node<>(val);
                nodes.put(val, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }

        }

        /**
         * 找根的同时, 需要将根下的所有后代节点, 直接挂到自己下面(打平)=>这样以后所有子节点向上只需要找一次即可找到根了.
         * 路径压缩.
         * M1: 栈方式; M2: 递归方式.
         * @param node
         * @return
         */
        public Node<V> findRoot(Node<V> node) {
            Node<V> vNode = parents.get(node);
            if (vNode==node) {
                return node; // 没有父=>根
            }

            Node<V> root = findRoot(vNode);
            parents.put(node, root); // 当前节点直接指向root
            return root;
        }

        /**
         * 循环方式
         * @param node
         * @return
         */
        public Node<V> findRoot2(Node<V> node) {
            Node<V> cur = node;
            Stack<Node<V>> stack = new Stack<>();
            while ((cur != parents.get(cur))) {
                stack.push(cur);
                cur = parents.get(cur);
            }
            // here, cur==root
            // 沿途所有节点直接指向root
            while (!stack.isEmpty()) {
                parents.put(stack.pop(), cur);
            }

            return cur;
        }

        /**
         * 判断 a,b是否在一个集合
         */
        public boolean isSameSet(V a, V b) {
            return findRoot(nodes.get(a)) == findRoot(nodes.get(b));
        }

        /**
         * 连接两个节点
         */
        public void union(V a, V b) {
            Node<V> aNode = nodes.get(a);
            Node<V> bNode = nodes.get(b);
            // 分别找到两个节点的根节点, 连接两个根节点, 即完成了"连接动作"
            Node<V> aRoot = findRoot(aNode);
            Node<V> bRoot = findRoot(aNode);
            // 小size的挂到大size下, 使得更少的节点找根的路径较长, 比如 100和5, 5挂到100下, 100个向上找一次即可, 5个向上找2次
            Integer aSize = sizeMap.get(aRoot);
            Integer bSize = sizeMap.get(bRoot);
            Node<V> big, small;
            if (aSize>bSize) {
                big = aRoot; small = bRoot;
            } else {
                big = bRoot; small = aRoot;
            }
            parents.put(small, big);
            sizeMap.put(big, aSize + bSize);
            sizeMap.remove(small);
        }
    }

    public static class Node<V> {
        public V value;

        public Node(V value) {
            this.value = value;
        }
    }

}
